// https://leetcode.cn/problems/maximize-win-from-two-segments/description/
// 2555 两个线段获得的最多奖品
/**
 * 
 * 在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。

你可以同时选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。

比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。
请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。
示例 1：

输入：prizePositions = [1,1,2,2,3,3,5], k = 2
输出：7
解释：这个例子中，你可以选择线段 [1, 3] 和 [3, 5] ，获得 7 个奖品。
示例 2：

输入：prizePositions = [1,2,3,4], k = 0
输出：2
解释：这个例子中，一个选择是选择线段 [3, 3] 和 [4, 4] ，获得 2 个奖品。
 */
/**
 * @param {number[]} prizePositions
 * @param {number} k
 * @return {number}
 */
var maximizeWin = function (prizePositions, k) {
    let indexSum = collectResult(prizePositions);
    let maxIndex = prizePositions[prizePositions.length - 1];
    let startIndex = prizePositions[0];

    const maxCount1 = getMaxCount(indexSum, startIndex, maxIndex, k);
    const maxCount2 = getMaxCount(indexSum, startIndex, maxIndex, k);

    console.log(`result is ${maxCount1 + maxCount2}`);

    return maxCount1 + maxCount2;
};

function getMaxCount(indexSum, startIndex, maxIndex, k) {
    let start = startIndex;
    let end = start + k;
    let maxCount = 0;
    let count = 0;

    for (let j = start; j <= start + k; j++) {
        if (indexSum[j] != undefined) {
            count += indexSum[j];
        }
    }

    maxCount = count;

    for (let i = start + 1; i <= Math.max(start + 1, maxIndex - k); i++) {
        if (indexSum[i - 1] != undefined) {
            count -= indexSum[i - 1];
        }

        if (indexSum[i + k] != undefined) {
            count += indexSum[i + k];
        }

        if (count > maxCount) {
            start = i;
            end = i + k;
            maxCount = count;
        }
    }

    for (let i = start; i <= end; i++) {
        indexSum[i] = 0;
    }

    return maxCount;
}

function collectResult(prizePositions) {
    let indexSum = {};

    prizePositions.forEach((element) => {
        if (indexSum[element] === undefined) {
            indexSum[element] = 1;
        } else {
            indexSum[element] += 1;
        }
    });

    return indexSum;
}

maximizeWin([1, 1, 2, 2, 3, 3, 5], 2); // 7
maximizeWin([1, 2, 3, 4], 0); // 2
maximizeWin(
    [
        2616, 2618, 2620, 2621, 2626, 2635, 2657, 2662, 2662, 2669, 2671, 2693,
        2702, 2713, 2714, 2718, 2730, 2731, 2750, 2756, 2772, 2773, 2775, 2785,
        2795, 2805, 2811, 2813, 2816, 2823, 2824, 2824, 2826, 2830, 2833, 2857,
        2885, 2898, 2910, 2919, 2928, 2941, 2942, 2944, 2965, 2967, 2970, 2973,
        2974, 2975, 2977, 3002, 3007, 3012, 3042, 3049, 3078, 3084, 3089, 3090,
        3094, 3097, 3114, 3124, 3125, 3125, 3144, 3147, 3148, 3174, 3197, 3255,
        3262, 3288, 3291, 3316, 3320, 3322, 3331, 3342, 3378, 3412, 3412, 3416,
        3420, 3427, 3428, 3446, 3452, 3472, 3479, 3483, 3488, 3500, 3516, 3522,
        3531, 3532, 3540, 3540, 3544, 3557, 3570, 3580, 3592, 3597, 3597, 3601,
        3615, 3631, 3640, 3645, 3673, 3677, 3681, 3683, 3685, 3718, 3738, 3746,
        3758, 3769, 3797, 3802, 3815, 3832, 3839, 3851, 3864, 3888, 3889, 3901,
        3902, 3910, 3913, 3933, 3940, 3961, 3974, 3988, 4003, 4013, 4019, 4023,
        4026, 4047, 4060, 4065, 4072, 4073, 4082, 4084, 4109, 4132, 4139, 4143,
        4145, 4146, 4155,
    ],
    6641
);
maximizeWin(
    [
        375344743, 375811382, 376205354, 376583225, 377326584, 377528242,
        377556486, 377561264, 377747991, 377749793, 377838108, 377905270,
        378225612, 378389478, 378638215, 379501835, 379550808, 380108794,
        380146950, 380691791, 381393652, 382408980, 382670758, 383132819,
        384531606, 384601605, 384619910, 384848369, 385221568, 385231233,
        385753380, 385949112, 386833113, 387371507, 387648433, 387669754,
        387712024, 387960080, 388599148, 388931923, 389889842, 390466891,
        390628019, 390915526, 391471142, 391481330, 391883528, 392131052,
        392170820, 392873875, 392948257, 393200244, 393217847, 393227344,
        393548051, 393564034, 394717709, 396648759, 397290396, 397473501,
        398172233, 398431650, 398509186, 398829475, 398890185, 399201278,
        399598370, 400335640, 400886541, 401423147, 401596279, 402068593,
        402900993, 403027769, 403515881, 404956177, 405354937, 406036459,
        406682171, 406818231, 407126246, 407374429, 408011409, 408535761,
        408642304, 408894488, 409787453, 409807299, 410313373, 410614153,
        410808004, 412195139, 412641197, 413922900, 414109622, 414287986,
        414382334, 414693905, 414876837, 414976334, 415371268, 415716409,
        416429736, 417258167, 417426100, 417635786, 418804503, 419050297,
        419773033, 419878382, 420064412, 420497879, 421027960, 421424811,
        422087830, 422107655, 423025413, 423083263, 423112230, 423298825,
        423787582, 423961843, 424292689, 424939243, 425056934, 426223721,
        426295609, 426567665, 426787636, 426941716, 427947471, 428503139,
        428511729, 428520675, 428605077, 428794088, 429514626, 429804206,
        430098631, 430158655, 430187406, 431583883, 431785301, 431926967,
        432049526, 432306436, 432312542, 432313473, 432578851, 432655672,
        432730640, 432869346, 432891421, 433292749, 433420800, 433969706,
        434257007, 434430199, 435164434, 435602256, 435627677, 435930182,
        436132585, 436349199, 437135467, 437454940, 437774216, 438159481,
        438169635, 438664688, 439265721, 439715813, 440271155, 441010442,
        441166897, 441192055, 441526923, 441602630, 442143100, 442983517,
        443071496, 443328899, 444772683, 444879199, 445810350, 445917622,
        445978681, 446227097, 446309463, 446647098, 446660098, 446962967,
        446983709, 447278253, 447387622, 447975621, 448104047, 448134985,
        449126767, 449355419, 450508025, 450608498, 450820492, 451893936,
        452096442, 452687744, 453609510, 453829020, 454334559, 454382390,
        454694452, 454779520, 455125333, 455286585, 456080969, 456618332,
        456657407, 456706375, 457622753, 457948197, 458337647, 458510749,
        458953193, 459062696, 459084205, 459219347, 459311702, 459548662,
        459549465, 459825411, 460486502, 460809812, 461672674, 461736577,
        462144905, 462163457, 462705146, 462799115, 462978062, 463075675,
        463405864, 464150809, 464381247, 464468421, 464610198, 465077145,
        465264285, 465490378, 465892133, 466142165, 466383208, 466589265,
        466623751, 466642223, 466849580, 467392187, 467473187, 467737515,
        467770346, 468391734, 468396254, 468597025, 468706659, 469545260,
        469548802, 470531856, 470542741, 471253163, 471465840, 471737215,
        471830132, 471986170, 472111291, 472895883, 473190408, 473759623,
        473819369, 474476756, 474721682, 475025035, 476043766, 476571257,
        476949002, 477983505, 477995897, 478330583, 478443218, 478544130,
        478654201, 479212071, 479478225, 479514198, 479651156, 479722039,
        479850621, 479962461, 480240876, 480739017, 480849313, 481243652,
        481535682, 482141304, 482672032, 483057639, 483090707, 483303439,
        483522540, 483863060, 484020556, 484447303, 484555767, 484891807,
        484930678, 485791276, 486086663, 486481282, 487117636, 487339158,
        488195829, 488425064, 488614205, 488865762, 489011683, 489415853,
        489698506, 490623722, 491078678, 491155152, 491486345, 491578202,
        491838937, 492031953, 492970749, 493351260, 493457725, 494074574,
        494269621, 494789844, 494946902, 495248135, 495386431, 495957495,
        496763514, 497038953, 497294685, 498395649, 498621425, 499151628,
        499908505, 500235558, 500249429, 501009330, 501968415, 502462284,
        502705458, 502850996, 502975948, 502996862, 503229333, 503305824,
        503476011, 503694479, 504502392, 504572661, 505026750, 505598419,
        505860413, 505947985, 506033217, 506379896, 506814214, 507063145,
        507229613, 507484911, 507509670, 508076993, 508356875, 508391331,
        508545177, 508904924, 509051708, 509426866, 510149081, 510550051,
        511307779, 511617039, 512319546, 512559298, 512588607, 512705920,
        512911566, 513030763, 513065181, 513341070, 513845222, 513935530,
        513974837, 515145391, 515431408, 515532844, 515556141, 516178966,
        516923647, 517363175, 517610088, 517753193, 518129924, 518251104,
        519053349, 519178507, 519586386, 519631377, 519815449, 520861973,
        521061436, 521390965, 521845209, 522627131, 523923949, 524275138,
        524313650, 524706243, 524800064, 525328862, 525525500, 525705965,
        526221370, 526791616, 526847612, 526915034, 527578210, 528211713,
        528265211, 528372502, 528880170, 528938383, 529446502, 529528273,
        530317143, 530415876, 531202886, 532006161, 532162179, 532308455,
        532612053, 533497184, 533741102, 534317878, 534529892, 535452515,
        535494236, 535833656, 536481616, 537282762, 537606885, 537653689,
        537672732, 537672816, 537822499, 537835973, 538592250, 538987852,
        541700470, 541925452, 542048479, 542316513, 543350704, 543721539,
        543784778, 544022143, 544328076, 544580127, 545419317, 545652938,
        546444569, 546605041, 547495534, 547508819, 548398765, 548453243,
        548471005, 549074107, 549115921, 549565220, 549609045, 549691959,
        550521237, 551256123, 551765796, 551836039, 552190804, 552208151,
        552555907, 552577264, 552631110, 552772714, 553645105, 554255016,
        554439844, 554517304, 554991642, 555126826, 555177263, 555776402,
        555936697, 555995953, 556063912, 556209379, 557827557, 559259489,
        559337656, 559518477, 562653900, 562722644, 566137440, 566334015,
        566479511, 566545447, 567244640, 567805121, 567862874, 567866338,
        567962873, 568000243, 568254541, 568520531, 568582931, 568781617,
        569284645, 570023442, 570864078, 571430710, 571700363, 572288554,
        572958785, 573342488, 574241106, 574396274, 575692079, 575759636,
        575934276, 576030593, 576099190, 576381414, 576597305, 576735021,
        577128503, 577549056, 578198224, 578604209, 578879551, 579297101,
        579327915, 579328534, 579436584, 579690565, 580161662, 580465749,
        580555114, 580607032, 580869317, 581015151, 581054006, 581740778,
        582049879, 582707046, 582791911, 582932696, 583849788, 583888998,
        583930305, 583950123, 584953605, 585065301, 585210530, 585211547,
        585636106, 585685042, 585695842, 585979096, 586410456, 586544943,
        586854190, 587389470, 588902969, 589110813, 589172115, 589442181,
        589491893, 589627942, 589717284, 590226577, 591062097, 591498207,
        591515537, 591961646, 592014281, 592148740, 592286436, 592310300,
        593246141, 593256206, 593380442, 593463818, 594781426, 594824070,
        594831879, 594931949, 595368996, 596616057, 596716001, 596766017,
        597704640, 598207133, 598404617, 599014207, 600293385, 600893195,
        601355588, 601401383, 601870213, 602179061, 602386885, 603285355,
        603673352, 603814135, 603889490, 604160860, 604312475, 604457867,
        604587468, 605534418, 606022456, 606182373, 606483037, 606543133,
        606620572, 606680214, 606754278, 606861176, 607638574, 607970824,
        608629492, 609078120, 609518013, 609543374, 609721759, 609815688,
        610025373, 610341639, 610601058, 610915945, 611205241, 611398319,
        611424055, 611560824, 612067602, 612361884, 613177111, 613268532,
        613316638, 613360679, 613481599, 613540965, 613576196, 613662913,
        614781590, 615234975, 615772253, 615839466, 616519630, 616566216,
        617672222, 618287514, 618331620, 619228897, 619790029, 620639284,
        621011016, 621204960, 621554920, 621656884, 621713132, 621746466,
        622014189, 622077255, 622105397, 623545203, 623741987, 623986256,
        624053130, 624056468, 624617896, 624919921, 625587862, 625995770,
        626489644, 626949220, 627095975, 627223355, 627599604, 628221303,
        628449345, 628533427, 628616044, 628676847, 628723633, 629309297,
        629995345, 630602404, 630718176, 631094359, 631165472, 631482602,
        631865374, 631908049, 632337805, 632384667, 632562050, 632937752,
        632944941, 633949052, 634216296, 634312014, 634497021, 635035374,
        635334368, 635437514, 635844654, 636487908, 636509466, 636544329,
        636635063, 636733046, 637404075, 637485348, 637761723, 638353788,
        639557577, 640338772, 641132684, 641179240, 641291929, 641581172,
        641929244, 642104635, 642242207, 642719168, 642733046, 643020637,
        643287367, 643306171, 643511443, 645013995, 645601298, 646723775,
        647025401, 647091716, 647549737, 647602032, 647745368, 648195732,
        648239529, 648291198, 648492767, 648628349, 648938617, 649232505,
        649542291, 649920714, 649992363, 650066607, 651391427, 651852353,
        652217492, 653360977, 653363896, 654667280, 654812987, 654875840,
        655303201, 655716834, 655833352, 655875258, 656629940, 656687292,
        656691516, 656768575, 657118644, 657519771, 657755248, 658727856,
        659290820, 659683824, 659947222, 661023468, 661799735, 663011594,
        663361297, 664668990, 665107775, 665157395, 665204395, 665268199,
        666226327, 666566906, 667469150, 667561265, 667845206, 668204698,
        668925972, 669141092, 669951127, 670017909, 670482257, 670623785,
        670636197, 671570168, 671684871, 671930196, 672671805, 673027659,
        673119830, 673162196, 673234493, 673316493, 673329275, 673432596,
        673544316, 673738935, 673939103, 674061518, 674757718, 675159973,
        675220679, 675436537, 675513175, 676290230, 676353888, 676975711,
        677248545, 677651077, 678210480, 678281195, 678469486, 679350651,
        679440193, 679712384, 679794445, 679995747, 680027679, 680126827,
        680258571, 680483943, 681092177, 681460555, 681500685, 681928438,
        681934149, 682058541, 682084906, 682184253, 682263189, 682756635,
        682918460, 682970775, 683411383, 684438392, 684512200, 684796193,
        684907127, 684991420, 685024043, 685151132, 685357964, 685466175,
        685542727, 685628248, 686199513, 686393669, 686667810, 687151730,
        687573563, 687767688, 688315254, 689097050, 689669555, 690075664,
        690195821, 690883841, 691044829, 691387338, 691410157, 692029721,
        692208321, 692475807, 692525097, 692622968, 692642614, 693725449,
        694012046, 694105886, 695248149, 695422111, 696120578, 696517217,
        696797852, 697455884, 697929593, 698208231, 698291130, 698325785,
        698897587, 699124433, 699140763, 699203146, 699590753, 700210933,
        700632895, 700746471, 700768506, 700773482, 701435056, 701490549,
        702167169, 702408048, 702594727, 702601892, 702930476, 703149836,
        703770797, 704035508, 704301769, 705318460, 705367634, 705374889,
        705680362, 705779949, 705865549, 706062106, 706785041, 707085704,
        708318577, 708630436, 708698070, 709363760, 709656921, 709718208,
        710177558, 710180281, 710680888, 710947453, 710955794, 711047125,
        711199046, 712103764, 712297542, 712441530, 712448521, 712968765,
        712998917, 713385290, 713585051, 713820360, 714237341, 714320431,
        714663700, 715239638, 715492814, 715681817, 715757996, 716457187,
        716492672, 716509274, 716745700, 716907444, 717911595, 718326366,
        718725158, 719711744, 719773658, 720200365, 720304182, 721080555,
        721375707, 721672298, 721816769, 722352866, 722525382, 723569379,
        724190317, 724282107, 724312445, 726082999, 726386683, 726953107,
        727096456, 727613551, 729390276, 729396314, 729937239, 730636535,
        730798866, 731192263, 731286811, 731762769, 732023214, 732425138,
        732652337, 732937629, 733192730, 733417087, 733988673, 734667968,
        735186603, 735732733, 735904246, 735946124, 736819009, 737076557,
        737378851, 737809387, 738332574, 739197874, 740379255, 741213342,
        741230007, 741419762, 741680130, 741792699, 742324623, 743638624,
        743719025, 743817400, 745334876, 745341428, 745538266, 745539016,
        745736581, 746260981, 746359496, 746689829, 747153988, 747834409,
        748492938, 748897793, 749073992, 749865861, 751189892, 751287234,
        751810001, 751920224, 752330766, 752497265, 752697708, 753138045,
        753518988, 754270893, 754703161,
    ],
    172
);
